A. Field of the Invention
This invention relates to a binary division circuit which performs division with floating point of fixed point numbers. In particular, a binary division circuit is disclosed which produces results that are compatible with current, as well as past, large scale data processing systems.
B. Prior Art
In the past, the division operation was most often performed in a digital data processing system using ordinary long hand division. That is, the division operation was accomplished by repetitively subtracting the divisor from the dividend until an insufficient quantity remains to perform another subtraction. The number of successful subtractions is, of course, the quotient. This method, along with a number of variations, comprise the general class of division methods known as subtractive divide methods. In particular, this method was used in the Control Data Corporation's Model 7600 Data Processing System and in the Sperry Corporation's Model 1108 Data Processing System.
There is another class of division methods coming into use in modern day data processing systems. This is the class of iterative divide methods. These iterative divide methods fall into two subclasses.
The first of this subclasses is known as the reciprocal method and utilizes a reciprocal unit. In this method an approximation of the reciprocal is computed by performing several special multiplication and subtraction operations. The result of that approximation is then multiplied by the dividend. This result is then an approximation of the quotient. The CRAY-1 Data Processing System has such a reciprocal unit in it.
In the second subclass of iterative division methods, the divisor is repetitively multiplied by a series of numbers. The product of this multiplication is a number that has the approximate value of one (1). The dividend is likewise multiplied by the same series of numbers and the product provides an approximation of the quotient. A variation of this method is used in the IBM Corporation's Model 360/91 Data Processing System.
These iterative division methods using the multiplication process came into use when fast multiplier circuits were initially developed. The iterative methods require special correction hardware in order to produce quotients that are compatible with quotients produced by the previously discussed subtractive division method. This fact is illustrated by two examples of these methods.
In the first example, three (3) is divided by three (3) using the reciprocal method. Long hand division, of course, gives an answer of one (1). However, the reciprocal of 3 is 0.3333 (to four decimal places). Multiplying 3 times 0.3333 gives a product of 0.9999, which is incorrect since it is less than 1.
In the second example, one-half (1/2) is divided by one-half (1/2) using the method described in the paper entitled "The IBM System/360 Model 91: Floating-Point Execution Unit", published in the IBM Technical Journal, January, 1967. In that method, both the dividend and the divisor are multiplied by the sequence 1+1/2, 1+1/4, 1+1/8, 1+1/16 . . . etc. This operation produces products of 3/4, 15/16, 63/64, . . . etc. Each of these products is less than 1, while, of course, the quotient produced by long-hand division is one (1).
A further unique iterative approach is disclosed herein, in which a novel multiplier augmentation is combined with a new quotient correction technique.